\section{Background}

\subsection{Blinded Signatures}
The idea of using blinded signature for anonymous payments originated with Chaum in 1983 \cite{chaum-blind}. We summarize Chaum's blinded signature below.
The following three functions make up the cryptosystem:
\begin{enumerate}
\item The signing function, $s'$, known only to the signer, and the corresponding publicly known inverse, $s$, with the property that $s(s'(x)) = s'(s(x)) = x$, and $s$ gives no clue about $s'$.
\item The commuting function $c$ and its inverse $c'$, both known only to the provider, such that $c'(s'(c(x))) = s'(x)$, and $c(x)$ and $s'$ give no information about $x$.
\item A redundancy checking predicate $r$, that checks for sufficient redundancy to make search for valid signatures impractical.
\end{enumerate}
The protocol proceeds as follows:
\begin{enumerate}
\item Provider chooses token $x$ such that $r(x)$ holds, forms the blinded token $c(x)$, and passes it to the signer.
\item Signer signs the token $c(x)$ by applying $s'$ and returns the signed blinded token $s'(c(x))$ to provider.
\item Provider applies $c'$ to the signed blinded token to get $c'(s'(c(x))) = s'(x)$, the signed token.
\item Ayone can verify that $s'(x)$ was signed by the signer, by applying the public key $s$ and checking that $r(s(s'(x)))$ holds.
\end{enumerate}
The scheme achieves the following security properties:
\begin{enumerate}
\item Digital signature - anyone can check that a signed token $s'(x)$ was indeed formed using the secret key of the signer $s'$.
\item Blind signature - the signer knows nothing about the correspondence between the set of signed blinded tokens $s'(c(x_i))$ and their counterparts the signed tokens $s'(x_i)$.
\item Conservation of signatures - given a signed blinded token $s'(c(x))$, the only signed token that the provider can produce is $s'(x)$. 
\end{enumerate}
With some care, this blinded signature scheme can be applied to ensure that a mixing server cannot discover a correlation between a user's input/output address pair in a Bitcoin mixing operation. 

\subsection{Related Works}

\subsection{Mixcoin}
Mixcoin is a protocol that requires no alterations to Bitcoin and intends to allow users to send coins anonymously.  It offers a cryptographic warranty that the server will send coins to the user’s output address, so that any user can incriminate the server if it does not comply.  However, Mixcoin is centralized, so the server can link users’ input and output addresses.

\subsection{CoinJoin/CoinShuffle}
CoinJoin is a decentralized protocol in which all users must sign a joint transaction \cite{coinjoin}. Users remain anonymous and their funds cannot be stolen, since a user will only provide its signature if they agree to the transaction. CoinJoin is vulnerable to a DoS by a single user if they refuse to provide a signature during the signing round of the protocol. The protocol CoinShuffle is built on CoinJoin. It ensures that a transaction will eventually go through by including a blaming process in which misbehaving users can be eliminated from future mixing attempts by the honest participants \cite{coinshuffle}.

\subsection{Secure multiparty sort}
Some schemes have been devised that use a form of secure multiparty sort to achieve anonymous mixing \cite{multiparty}.  Users provide an input address and an output address.  The input addresses and output addresses are sorted separately using the secure multiparty sort, a decentralized sorting algorithm.  Each input address will have a corresponding output address of another user, defined as the output address at the same index of the input address in the sorted lists.  Since there is a one-to-one relationship between input addresses and output addresses, each user sends a chuck size of bitcoins from their input address to the corresponding output address in the sorted list.  However, this is still vulnerable to a DoS by a single user, as a user can join but not send the chuck size of bitcoins.

